package algorithm.dynamic_programming;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class PrintAllSubsquences {
    public static List<String> subs(String s){
        ArrayList<String> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        process1(list, 0, chars, "");
        return list;
    }

    public static void process1(ArrayList<String> ans, int index, char[] str, String path){
        if(index == str.length){
            ans.add(path);
            return;
        }
        process1(ans, index + 1, str, path);
        process1(ans, index + 1, str, path + str[index]);
    }

    public static HashSet<String> subNorepeat(String s){
        HashSet<String> set = new HashSet<>();
        char[] chars = s.toCharArray();
        process2(set, 0, chars, "");
        return set;
    }

    public static void process2(HashSet<String> set, int index, char[] str, String path){
        if(index == str.length){
            set.add(path);
            return;
        }
        process2(set, index + 1, str, path);
        process2(set, index + 1, str, path + str[index]);
    }

    public static void main(String[] args) {
        String s = "aab";
        HashSet<String> set = subNorepeat(s);
        List<String> list = subs(s);
        System.out.println(set);
        System.out.println(list);
    }

}
